package org.basis.algorithm.tree;

import org.basis.algorithm.tree.common.Node;

import java.util.HashMap;
import java.util.LinkedList;

/**
 * 是否是满二叉树
 *
 * @author Mr_wenpan@163.com 2021/12/22 11:35
 */
public class CheckFullBinaryTree {

    public static void main(String[] args) {

    }

    public static boolean isFbt(Node head) {
        if (head == null) {
            return true;
        }
        // 这里采用宽度优先遍历求树的节点个数和高度
        HashMap<Node, Integer> map = new HashMap<>();
        LinkedList<Node> queue = new LinkedList<>();
        queue.add(head);
        // 头节点属于第一层
        map.put(head, 1);
        // 树高度
        int high = 1;
        // 节点个数统计
        int count = 1;

        while (!queue.isEmpty()) {
            Node poll = queue.poll();
            Node left = poll.left;
            Node right = poll.right;
            if (high != map.get(poll)) {
                high++;
            }
            if (left != null) {
                queue.add(left);
                map.put(left, map.get(poll) + 1);
                count++;
            }
            if (right != null) {
                queue.add(right);
                map.put(right, map.get(poll) + 1);
                count++;
            }
        }

        // 通过公式 n = 2^k - 1 计算
        int n = (1 << high) - 1;
        return n == count;
    }
}
